package class07;

/**
 *
 * 二叉树的先序,中序,后序遍历
 * 先序:任何子树的处理顺序都是,先头结点,再左子树,然后右子树
 * 中序:任何子树的处理顺序都是,先左子树,再头结点,然后右子树
 * 后序:任何子树的处理顺序都是,先左子树,再右子树,然后头结点
 *
 *      1
 *   2     3
 *  4 5   6  7
 *
 *  先: 1 2 4 5 3 6 7
 *  中: 4 2 5 1 6 3 7
 *  后: 4 5 2 6 7 3 1
 */
public class Code01_RecursiveTraversalBT {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int v) {
			value = v;
		}
	}

	public static void f(Node head) {
		if (head == null) {
			return;
		}
		//利用了递归序(每个节点会到达3次)
		//1 2 4 4 4 2 5 5 5 2
		//1 3 6 6 6 3 7 7 7 3
		//1
		// 1 先序(第一次到达一个节点即打印)
		f(head.left);
		// 2 中序(第二次到达一个节点即打印)
		f(head.right);
		// 3 后序(第三次到达一个节点即打印)
	}

	// 先序打印所有节点
	public static void pre(Node head) {
		if (head == null) {
			return;
		}
		System.out.println(head.value);
		pre(head.left);
		pre(head.right);
	}

	public static void in(Node head) {
		if (head == null) {
			return;
		}
		in(head.left);
		System.out.println(head.value);
		in(head.right);
	}

	public static void pos(Node head) {
		if (head == null) {
			return;
		}
		pos(head.left);
		pos(head.right);
		System.out.println(head.value);
	}

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		head.right.right = new Node(7);

		pre(head);
		System.out.println("========");
		in(head);
		System.out.println("========");
		pos(head);
		System.out.println("========");

	}

}
